package 链表;

import java.awt.*;

/**
 * 反转一个单链表。
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 * <p>
 * 由于链表只能从前往后遍历
 * 1->2->3->4->5->NULL
 * 1->null
 * 2->1->null
 * 3->2->1->null
 * 4->3->2->1->null
 * 5->4->3->2->1->null
 * https://leetcode-cn.com/problems/reverse-linked-list/
 */
public class _206_反转链表 {
    public static void main(String[] args) {
        ListNode first = new ListNode(10);
        ListNode second = new ListNode(11);
        ListNode third = new ListNode(12);
        ListNode four = new ListNode(13);
        ListNode five = new ListNode(14);
        first.next = second;
        second.next = third;
        third.next = four;
        four.next = five;
        LinkedListUtils.printNode(first);
        ListNode newHead = reverseList02(first);
        LinkedListUtils.printNode(newHead);
    }

    /**
     * 递归解法
     */
    public static ListNode reverseList01(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode node = reverseList01(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }

    public static ListNode reverseList02(ListNode head) {
        // 前驱节点
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            // 保存下一个节点
            ListNode tempNode = cur.next;
            // 将当前节点的下一个节点指向前一个节点
            cur.next = prev;
            // 前一个节点和当前节点都向后移动一位
            prev = cur;
            cur = tempNode;
        }
        return prev;
    }
}
